package lc;
import java.util.*;
import org.junit.*;

import util.BracketUtils;
public class Ex56 {
    class Solution {
        public int[][] merge(int[][] intervals) {
            Arrays.sort(intervals, (n1, n2) -> {
                if (n1[0] != n2[0]) {
                    return n1[0] - n2[0];
                } else {
                    return n1[1] - n2[1];
                }
            });
            Stack<int[]> stack = new Stack<>();
            for (int i = 0; i < intervals.length; i++) {
                if (stack.isEmpty() || stack.peek()[1] < intervals[i][0]) {
                    stack.push(intervals[i]);
                } else {
                    int[] last = stack.pop();
                    stack.push(new int[]{last[0], intervals[i][1]});
                }
            }
            int[][] res = new int[stack.size()][2];
            int i = res.length - 1;
            while (!stack.isEmpty()) {
                res[i--] = stack.pop();
            }
            return res;
        }
    }
    

    @Test
    public void test() {
        Solution s = new Solution();
        int[][] nums = BracketUtils.to2DArray("[[2,3],[2,2],[3,3],[1,3],[5,7],[2,2],[4,6]]");
        System.out.println(Arrays.deepToString(s.merge(nums)));
        
    }
}
